% Helper function to determine if G* is Hamiltonian
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% function isHamiltonianFlag =
% isHamiltonianHelper(Gstar,visitedArray,currentNode,varargin);
%  
%   This function will print out an output for if the graph Gstar is
%   Hamiltonian through a fairly trivial algorithm. This will probably wind
%   up being used as another helper function.
%
%   INPUTS:     Gstar - graph created from G after removing all pendant
%                       vertices (made from GtoGstar())
%               
%   OUTPUTS:    isHamiltonianFlag - is 1 if graph is Hamiltonian, else 0            
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function isHamiltonianFlag = isHamiltonianHelper(Gstar,visitedArray,currentNode,xmax,ymax,varargin);




isHamiltonianFlag = 0;
%[xmax ymax]=size(Gstar);

visitedArray(currentNode) = 1; 

% First we check to see if all of them are visited.
if (sum(visitedArray) == xmax),
    if (Gstar(currentNode,1) == 1),
        toc
        sprintf('G* is hamiltonian by brute force search')
        isHamiltonianFlag = 1;
    end;
    
else
    % Now we need to loop through all of the indexes 
    for x = 1:xmax
        % if the edge exists but we haven't visited the node
        if (Gstar(currentNode,x) == 1 && visitedArray(x) == 0 && isHamiltonianFlag ~= 1)
            isHamiltonianFlag = isHamiltonianHelper(Gstar,visitedArray,x,xmax,ymax);
        end;
    end;
end;